/*
375. 猜数字大小 II   https://leetcode.cn/problems/guess-number-higher-or-lower-ii/
中等 2024/11/18

*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int getMoneyAmount(int n) {
        // 创建一个大小为 (n+1) * (n+1) 的 DP 表
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        
        // 从长度为 2 到 n 的区间逐步计算
        for (int len = 2; len <= n; ++len) {
            for (int i = 1; i <= n - len + 1; ++i) {
                int j = i + len - 1;
                dp[i][j] = INT_MAX;  // 初始化为一个大的数
                // 在区间 [i, j] 中尝试猜测每个数字 x
                for (int x = i; x <= j - 1; ++x) {
                    // 对于每个 x，选择最大值并加上 x 的代价
                    dp[i][j] = min(dp[i][j], x + max(dp[i][x-1], dp[x+1][j]));
                }
            }
        }
        
        return dp[1][n];
    }
};
int main()
{
    Solution solution;

    int n;
    cout << "请输入数字范围的上限n：";
    cin >> n;

    int result = solution.getMoneyAmount(n);

    cout << "能够确保获胜的最小现金数为：" << result << endl;

    return 0;
}